package AboutSort;

public class QuickSort {

    public static void sort(int[] nums){
        trueSort(0,nums.length - 1,nums);
    }

    public static void trueSort(int l , int r , int[] nums){
        if(l > r){
            return;
        }
        int base = nums[l];
        int i = l;
        int j = r;
        while(i < j){
            //从右边开始走
            while(i < j && nums[j] >= base){
                j--;
            }

            //接下来左边开始走
            while(i < j && nums[i] <= base){
                i++;
            }

            //到了这里说明已经找到了要交换的值
            if(i < j){
                int temp = nums[i];
                nums[i] = nums[j];
                nums[j] = temp;
            }

        }

        //交换基值
        nums[l] = nums[i];
        nums[i] = base;

        trueSort(l,i - 1,nums);
        trueSort(i + 1 , r , nums);
    }

    public static void main(String[] args){
        int[] nums = {7,1,0,0,2,1,3,8,1};
        sort(nums);
        for(int i : nums){
            System.out.print(i+" ");
        }
    }
}
